#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int sl2dec(const char *an, const char *language);
static char *dec2tl(int dec, const char *language);

static inline int power_diy(int x, int y)
{
	int i, ret = 1;
	for (i = 0; i < y; i++) 
		ret *= x;
	return ret;
}

int main(int argc, char **argv)
{
	int n, i;
	char buffer[1024];
	char *sl = NULL, *tl = NULL, *ans = NULL;
	int an;
	char *result = NULL;

	fgets(buffer, sizeof buffer, stdin);
	sscanf(buffer, "%d", &n);
	for (i = 0; i < n; i++) {
		fgets(buffer, sizeof buffer, stdin);
		buffer[strlen(buffer) - 1] = '\0';
		tl = strrchr(buffer, ' ');
		*tl = '\0';
		tl++;
		sl = strrchr(buffer, ' ');
		*sl = '\0';
		sl++;
		ans = buffer;
		an = sl2dec(ans, sl);
		result = dec2tl(an, tl);
		printf("Case #%d: %s\n", i + 1, result);
		free(result);
	}
	return 0;
}

static int sl2dec(const char *an, const char *language)
{
	int ret = 0;
	int an_digit = strlen(an), i;
	int lan_digit = strlen(language);
	char *p = NULL;

	for (i = 0; i < an_digit - 1; i++) {
		ret += (lan_digit - 1) * power_diy(lan_digit, i);
	}
	p = strchr(language, an[0]);
	ret += (p - language - 1) * power_diy(lan_digit, an_digit - 1);
	for (i = 1; i < an_digit; i++) {
		p = strchr(language, an[i]);
		ret += (p - language) * power_diy(lan_digit, an_digit - i - 1);
	}
	ret++;
	return ret;
}

static char *dec2tl(int dec, const char *language)
{
	char *ret = NULL;
	int lan_digit = strlen(language);
	int x = dec, y, i = 0, j;
	char tmp;
	
	ret = malloc(1024);
	memset(ret, 0, 1024);
	if (!x) {
		ret[0] = language[0];
		i++;
	}
	while (x) {
		y = x % lan_digit;
		ret[i] = language[y];
		i++;
		x /= lan_digit;
	}
	for (j = 0; j < i / 2; j++) {
		tmp = ret[j];
		ret[j] = ret[i - 1 - j];
		ret[i - 1 - j] = tmp;
	}
	return ret;
}
